
/**
 * 粉刷房子
 *  假如有⼀排房⼦，共 n 个，每个房⼦可以被粉刷成红⾊、蓝⾊或者绿⾊这三种颜⾊中 的⼀种，你需要粉
 *  刷所有的房⼦并且使其相邻的两个房⼦颜⾊不能相同。
 *  当然，因为市场上不同颜⾊油漆的价格不同，所以房⼦粉刷成不同颜⾊的花费成本也 是不同的。每个房
 *  ⼦粉刷成不同颜⾊的花费是以⼀个 n x 3 的正整数矩阵 costs 来表 ⽰的。
 *  例如， costs[0][0] 表⽰第 0 号房⼦粉刷成红⾊的成本花费； costs[1][2] 表⽰第 1 号 房⼦粉刷成绿⾊的
 *  花费，以此类推。 请计算出粉刷完所有房⼦最少的花费成本。
 */

// f(i, j): 第i个房子涂j颜色最小花费
function minCost(costs) {
  let n = costs.length;
  let f = new Array(n);
  for (let i = 0; i < n; i++) f[i] = new Array(3);

  f[0][0] = costs[0][0];
  f[0][1] = costs[0][1];
  f[0][2] = costs[0][2];

  for (let i = 1; i < n; i++) {
    f[i][0] = Math.min(f[i - 1][1], f[i - 1][2]) + costs[i][0];
    f[i][1] = Math.min(f[i - 1][0], f[i - 1][2]) + costs[i][1];
    f[i][2] = Math.min(f[i - 1][0], f[i - 1][1]) + costs[i][2];
  }

  return Math.min(f[n - 1][0], f[n - 1][1], f[n - 1][2])
}

let costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]];
console.log(minCost(costs));

/**
 * 动归
 */

function getMinGet1000(arr) {
  const n = arr.length;
  const dp = []; // i件物品，总值为j, 最小组合
  for (let i = 1; i <= n; i++) {
    for (let j = 1000; j <= 11000; j++) { // j: 背包重量
      dp[i][j] = dp[i - 1][j]; // 不选当前物品
      if (j >= arr[i]) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);
    }
  }
  return dp[arr.length][0];
}